class Solution {
    public:
        vector<int> minCosts(vector<int>& cost) {
            int n = cost.size();
            vector<int> ans(n);
            int a = INT_MAX;
            for(int i = 0;i < n;i++){
                if(a > cost[i]) a = cost[i];
                ans[i] = a;
            }
            return ans;
        }
    };
    class Solution {
        public:
            int longestPalindrome(string s, string t) {
                int n = s.size(), m = t.size(), ans = 0;
                int a = 0, b = 0;
                vector<vector<int>> dps(n, vector<int>(n)), dpt(m, vector<int>(m)),
                    dp(n, vector<int>(m));
                vector<int> maps(n), mapt(m);
                for (int i = 0; i < n; i++) {
                    for (int j = i; j >= 0; j--) {
                        if (s[i] == s[j] && (i - j < 3 || dps[i - 1][j + 1] != 0))
                            dps[i][j] = i - j + 1, a = max(a, dps[i][j]),
                            maps[j] = max(maps[j], dps[i][j]);
                    }
                }
                for (int i = 0; i < m; i++) {
                    for (int j = i; j >= 0; j--) {
                        if (t[i] == t[j] && (i - j < 3 || dpt[i - 1][j + 1] != 0))
                            dpt[i][j] = i - j + 1, b = max(b, dpt[i][j]),
                            mapt[i] = max(mapt[i], dpt[i][j]);
                    }
                }
                for (int left = n - 1; left >= 0; left--) {
                    for (int right = 0; right < m; right++) {
                        int sright = 0, tleft = 0;
                        if (left != n - 1) {
                            sright = maps[left + 1];
                            // for (int i = 0; i < n; i++)
                            //     sright = max(sright, dps[i][left + 1]);
                        }
                        if (right != 0) {
                            tleft = mapt[right - 1];
                            // for (int i = 0; i < m; i++)
                            //     tleft = max(tleft, dpt[right - 1][i]);
                        }
                        if (s[left] == t[right]) {
                            if (left != n - 1 && right != 0) {
                                dp[left][right] = dp[left + 1][right - 1] + 2;
                            }
                            dp[left][right] =
                                max(dp[left][right],
                                    max(sright, tleft) + (s[left] == t[right] ? 2 : 0));
                        }
                        ans = max(ans, dp[left][right]);
                    }
                }
                // int a = dps[n - 1][0],b = dpt[m - 1][0];
                return max({ans, a, b});
            }
        };